﻿//给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
//
//输入: nums = [2, 2, 3, 4]
//输出 : 3
//解释 : 有效的组合是 :
//	2, 3, 4 (使用第一个 2)
//	2, 3, 4 (使用第二个 2)
//	2, 2, 3
//
//输入 : nums = [4, 2, 3, 4]
//输出 : 4
//
//提示 :
//	1 <= nums.length <= 1000
//	0 <= nums[i] <= 1000


class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 1.排序

        sort(nums.begin(), nums.end());
        int n = nums.size(), ret = 0;
        // 2.从⼩到⼤枚举所有的三元组

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    // 当最⼩的两个边之和⼤于第三边的时候，统计答案

                    if (nums[i] + nums[j] > nums[k])
                        ret++;
                }
            }
        }
        return ret;
    }
};